package origami;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * Created by Tzachi on 06/11/2014.
 *
 */
public class Tests {

    ICycleRecognition cycleRecognition;
    /**
     * Assumptions:
     * 1. Graph is fully connected (possible to reach from root to any node)
     * 2. When colors are used, all nodes start as white
     * 3. No more than one directed edge between a source and destination
     */

    @Before
    public void before(){
//        cycleRecognition = new ColorRecursiveMethod();
//        cycleRecognition = new IterativeMethod();
        cycleRecognition = new MemoryRestrictedMethod();
    }

    /**
     * input: null graph
     * output: false
     */
    @Test
    public void nullGraph_returnFalse() {
        Assert.assertFalse(cycleRecognition.findLoop(null));
    }

    /**
     * input: single node graph without children
     * output: false
     */
    @Test
    public void singleNode_noChildren_returnFalse() {
        Node nodeA = new Node("A");
        Assert.assertFalse(cycleRecognition.findLoop(nodeA));
    }

    /**
     * input: single node graph with self pointing child (loop size 1)
     * output: true
     */
    @Test
    public void singleNode_pointsItself_returnTrue() {
        Node nodeA = new Node("A");
        nodeA.getChildren().add(nodeA);
        Assert.assertTrue(cycleRecognition.findLoop(nodeA));
    }

    /**
     * input: 2 nodes, one edge between them
     * output: false
     */
    @Test
    public void twoNodes_singleEdge_returnFalse() {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        nodeA.getChildren().add(nodeB);
        Assert.assertFalse(cycleRecognition.findLoop(nodeA));
    }

    /**
     * back edge
     * input: 2 nodes, each pointing to the other (loop size 2)
     * output: true
     */
    @Test
    public void twoNodes_eachPointsToTheOther_returnFalse() {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        nodeA.getChildren().add(nodeB);
        nodeB.getChildren().add(nodeA);
        Assert.assertTrue(cycleRecognition.findLoop(nodeA));
    }

    /**
     * input: 3 nodes, 2 edges (2 children to root - 2 tree edges)
     * output: false
     */
    @Test
    public void threeNodes_twoChildren_returnTrue() {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");
        nodeA.getChildren().add(nodeB);
        nodeA.getChildren().add(nodeC);
        Assert.assertFalse(cycleRecognition.findLoop(nodeA));
    }

    /**
     * back edge
     * input: 3 nodes as list, last points back to root (loop size > 2)
     * output: true
     */
    @Test
    public void threeNodes_lastPointsToHead_returnTrue() {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");
        nodeA.getChildren().add(nodeB);
        nodeB.getChildren().add(nodeC);
        nodeC.getChildren().add(nodeA);
        Assert.assertTrue(cycleRecognition.findLoop(nodeA));
    }

    /**
     * forward edge
     * input: 3 nodes as list, first also points to last
     * output: true
     */
    @Test
    public void threeNodes_headPointsToLast_returnFalse() {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");
        nodeA.getChildren().add(nodeB);
        nodeB.getChildren().add(nodeC);
        nodeA.getChildren().add(nodeC);
        Assert.assertFalse(cycleRecognition.findLoop(nodeA));
    }

    /**
     * cross edge
     * input: 3 nodes, 3 edges, not creating a loop (a->b, a->c , c->b)
     * output: false
     */
    @Test
    public void threeNodes_crossEdge_returnFalse() {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");
        nodeA.getChildren().add(nodeB);
        nodeA.getChildren().add(nodeC);
        nodeC.getChildren().add(nodeB);
        Assert.assertFalse(cycleRecognition.findLoop(nodeA));
    }

    /**
     * back edge
     * input: 3 nodes, 3 edges, loop does not start at root
     * output: true
     */
    @Test
    public void threeNodes_loopNotStartingAtRoot_returnFalse() {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");
        nodeA.getChildren().add(nodeB);
        nodeB.getChildren().add(nodeC);
        nodeC.getChildren().add(nodeB);
        Assert.assertTrue(cycleRecognition.findLoop(nodeA));
    }

    /**
     * input: 4 nodes, 2 cycles (2 back edges)
     * output: true
     */
    @Test
    public void multipleCycles_returnTrue(){
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");
        Node nodeD = new Node("C");
        nodeA.getChildren().add(nodeB);
        nodeB.getChildren().add(nodeC);
        nodeC.getChildren().add(nodeA);
        nodeD.getChildren().add(nodeB);
        Assert.assertTrue(cycleRecognition.findLoop(nodeA));
        System.out.println();
    }


    /**
     * back edge and forward edge
     * input: loop does not start at root, root has forward edge to a node in cycle
     * output: true
     */
    @Test
    public void threeNodes_backAndForwardEdge_returnFalse() {
        Node nodeA = new Node("A");
        Node nodeD = new Node("D");
        Node nodeH = new Node("H");
        nodeA.getChildren().add(nodeD);
        nodeD.getChildren().add(nodeH);
        nodeH.getChildren().add(nodeD);
        nodeA.getChildren().add(nodeH);
        Assert.assertTrue(cycleRecognition.findLoop(nodeA));
    }
}
